

import java.util.*;
class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    /** Initialize your data structure here. */
    public MyStack() {
        this.queue1=new LinkedList<>();
        this.queue2=new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        if(this.empty()){
            this.queue1.offer(x);
        }else if(!this.queue1.isEmpty()){
            this.queue1.offer(x);
        }else{
            this.queue2.offer(x);
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if(this.empty()){
            return -1;
        }
        if(!this.queue1.isEmpty()){
            int size=this.queue1.size();
            for(int i=0;i<size-1;i++){
                this.queue2.offer(this.queue1.poll());
            }
            return this.queue1.poll();
        }else{
            int size=this.queue2.size();
            for(int i=0;i<size-1;i++){
                this.queue1.offer(this.queue2.poll());
            }
            return this.queue2.poll();
        }
    }

    /** Get the top element. */
    public int top() {
        if(this.empty()){
            return -1;
        }
        if(!this.queue1.isEmpty()){
            int size=this.queue1.size();
            int x=-1;
            for(int i=0;i<size;i++){
                x=this.queue1.poll();
                this.queue2.offer(x);
            }
            return x;
        }else{
            int size=this.queue2.size();
            int x=-1;
            for(int i=0;i<size;i++){
                x=this.queue2.poll();
                this.queue1.offer(x);
            }
            return x;
        }
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        if(this.queue1.isEmpty()&&this.queue2.isEmpty()){
            return true;
        }
        return false;
    }
}













class Solution1 {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<Character>();
        int len=s.length();
        for(int i=0;i<len;i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='{'||ch=='[') {
                stack.push(ch);
            }else {
                if(stack.empty()){
                    return false;
                }
                char a=stack.peek();
                if((a=='{'&&ch=='}')||(a=='('&&ch==')')||(a=='['&&ch==']')){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if(!stack.empty()){
            return false;
        }
        return true;
    }
}





public class CatDogAsylum {
    public ArrayList<Integer> asylum(int[][] ope) {
        // write code here
        ArrayList<Integer> list=new ArrayList<>();
        ArrayList<Integer> tmp=new ArrayList<>();
        for(int i=0;i<ope.length;i++){
            if(ope[i][0]==1){
                tmp.add(ope[i][1]);
            }else{
                if(ope[i][1]==0){
                    list.add(tmp.remove(0));
                }else if(ope[i][1]<0){
                    for(int j=0;j<tmp.size();j++){
                        if(tmp.get(j)<0){
                            list.add(tmp.remove(j));
                            break;
                        }
                    }
                }else{
                    for(int j=0;j<tmp.size();i++){
                        if(tmp.get(j)>0){
                            list.add(tmp.remove(j));
                            break;
                        }
                    }
                }
            }
        }
        return list;
    }
}




public class Joseph {
    public int getResult(int n) {
        // write code here
        return func(n,2);
    }
    public int func(int n,int m){
        int tmp=n%m==0?n/m:n/m+1;
        if(tmp<=m+1){
            return (tmp-1)*m+1;
        }
        int f=func(tmp,m+1);
        return (f-2)*m+1;
    }
}






class RecentCounter {
    public Queue<Integer> queue;
    public RecentCounter() {
        this.queue=new LinkedList<Integer>();
    }
    public int ping(int t) {
        this.queue.offer(t);
        while(this.queue.peek()<t-3000){
            this.queue.poll();
        }
        return this.queue.size();
    }
}









class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> stacks=new Stack<>();
        Stack<Character> stackt=new Stack<>();
        int lens=s.length();
        int lent=t.length();
        for(int i=0;i<lens;i++){
            char ch=s.charAt(i);
            if(ch=='#'){
                if(!stacks.empty()){
                    stacks.pop();
                }
            }else{
                stacks.push(ch);
            }
        }
        for(int i=0;i<lent;i++){
            char ch=t.charAt(i);
            if(ch=='#'){
                if(!stackt.empty()){
                    stackt.pop();
                }
            }else{
                stackt.push(ch);
            }
        }
        if(stacks.size()!=stackt.size()){
            return false;
        }
        while(!stacks.empty()&&!stackt.empty()){
            if(stacks.pop()!=stackt.pop()){
                return false;
            }
        }
        return true;
    }
}










class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> stack=new Stack<>();
        int count=0;
        for(String str : ops){
            if("+".equals(str)){
                int sum1=stack.pop();
                int sum2=stack.peek();
                stack.push(sum1);
                stack.push(sum1+sum2);
            }else if("D".equals(str)){
                int tmp=stack.peek();
                stack.push(tmp*2);
            }else if("C".equals(str)){
                stack.pop();
            }else{
                stack.push(Integer.parseInt(str));
            }
        }
        while(!stack.isEmpty()){
            count+=stack.pop();
        }
        return count;
    }
}









public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack=new Stack<>();
        int popIndex=0;
        int pushIndex=0;
        while(pushIndex<pushA.length){
            if(!stack.empty()&&stack.peek()==popA[popIndex]){
                stack.pop();
                popIndex++;
            }else{
                stack.push(pushA[pushIndex]);
                pushIndex++;
            }
        }
        while(!stack.empty()){
            if(stack.peek()==popA[popIndex]){
                stack.pop();
                popIndex++;
            }else{
                return false;
            }
        }
        return true;
    }
}



class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack=new LinkedList<>();
        int len=tokens.length;
        for(int i=0;i<len;i++){
            String str=tokens[i];
            if(isNumber(str)){
                stack.push(Integer.parseInt(str));
            }else{
                int a=stack.pop();
                int b=stack.pop();
                switch(str){
                    case "+":
                        stack.push(b+a);
                        break;
                    case "-":
                        stack.push(b-a);
                        break;
                    case "*":
                        stack.push(b*a);
                        break;
                    case "/":
                        stack.push(b/a);
                        break;
                    default :
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String str){
        return !("+".equals(str)||"-".equals(str)||"*".equals(str)||"/".equals(str));
    }
}